package 代码随想录.链表;

public class _6删除链表的倒数第N个节点 {
    /**
     * 19. 删除链表的倒数第 N 个结点
     * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
     * 给你一个链表，删除链表的 倒数 第 n 个结点，并且返回链表的头结点。
     */
    //快慢指针
    public ListNode removeNthFromEnd(ListNode head, int n){
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;
        //只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n  ; i++){
            fastIndex = fastIndex.next;
        }
        while (fastIndex.next != null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }
        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

    //计算节点总数法
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if(head==null)
            return null;
        ListNode cur = head;
        int cnt = 0;
        while(cur!=null){
            cnt++;
            cur = cur.next;
        }
        ListNode res = new  ListNode(0);
        res.next = head;
        cur = res;
        for(int i=1;i<=cnt-n;i++)
            cur = cur.next;
        if(cur.next!=null)
            cur.next = cur.next.next;
        return res.next;
    }
}
